#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

int decodeString(const string &s)
{
    if (s.size() == 0) return 0;
    
    string str2 = "10" + s;
    const char *str = str2.c_str();

    int a = 1, b = 1, c;

    str += 2;
    while (*str) {
        c = 0;
        if (*(str-1) == '1' || (*(str-1) == '2' && *str <= '6'))
            c += a;
        if (*str != '0') 
            c += b;
        a = b;
        b = c;
        str++;
    }
    return c;
}

inline bool valid(char c,char v) {return c=='1'||(c=='2'&&v<='6');}
inline bool valid(char c) {return c!='0';}
//from mitbbs longway2008 
int decodeString2(const string & s)
{
    char c1('0');
    int  n0(1),  n1(1), n(1);
    for (int i=0; i<s.size() && n>0; ++i) {
        n = n0*valid(c1,s[i]) + n1*valid(s[i]);
        n0 = n1; n1 = n;
        c1 = s[i]; 
    }
    return n; 
}

//from mitbbs qqfly original 
unsigned int decodeString3(char const* n_string) {
    if (!n_string) return 0;
    int n = 1; // strlen(n_string);
    if (n==1) {
        if(n_string[0]=='0') return 0; // not valid
        else return 1;
    }
    vector<int> num(n, 0);
    char *p = (char *) n_string;
    if (p[0] == '0') return 0; // not valid
    else num[0] = 1;
    if (p[1]!='0') num[1]+=num[0];
    if (p[0]=='1' || p[0]=='2' && p[1]<='6') num[1]++;
    for (int i=2; i<n; i++) {
        if (p[i]!='0') num[i]+=num[i-1];
        if (p[i-1]=='1' || p[i-1]=='2'&&p[i]<='6') num[i] += num[i-2];
    }
    return num[n-1];
}

//code from 1337
int cache[512];
int solve(const string &num, int idx) {
    if (cache[idx] != -1) return cache[idx];
    if (idx == num.length()) return 1;
    if (num[idx] == '0') return 0;
    if (idx == num.length()-1) return 1;

    int count = solve(num, idx+1);
    if (num[idx] == '1' || (num[idx] == '2' && num[idx+1] <= '6'))
    count += solve(num, idx+2);

    cache[idx] = count;
    return count;
}
                                                                              
int decodeString4(const string &num) {
    for (int i = 0; i < 512; i++)
    cache[i] = -1;

    if (num.length() == 0)
        return 0;
    return solve(num, 0);
}

int main(int argc, char **argv)
{
    map<char , int> myMap;
    srand ( time(NULL) );
    for (int i = 0; i < 26; i++) {
       myMap['a'+i] = i + 1; 
    }
  
    stringstream ss; 
    for (int i = 0; i < 26; i++) {
        int index = rand()%26;
        int digit = myMap['a' + index];
        ss << digit;
    }

    //int count = decodeString("7101718826166131941218111422617611201826163");
    int count = decodeString("112");
    cout << count << endl;
}
